﻿// Copyright (c) 2011 Dan Popick

// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:

// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using Open.Web.Stijl;

namespace Open.Web.Stijl.Partitioning
{
	public class FactorSet
	{
		/// <summary>
		/// Primes up to 500
		/// </summary>
		static int[] _primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499 };

		public int[] Factors { get; set; }
		public int FactorCount { get; set; }
		public int Size { get; set; }
		public bool IsFactorizable { get; protected set; }

		protected FactorSet() { }
		public FactorSet(int[] factors, int size)
		{
			Factors = factors;
			Size = size;
			FactorCount = factors == null ? 0 : factors.Sum();
			IsFactorizable = true;
		}
		public FactorSet(FactorSet set)
		{
			Factors = set.Factors;
			Size = set.Size;
			FactorCount = set.FactorCount;
			IsFactorizable = set.IsFactorizable;
		}

		public virtual string Log(int indentChars)
		{
			string indent = new String(' ', indentChars);
			return String.Format(indent + "factorSize: " + Size.ToString());
		}

		protected void InitializeFromNumber(int num)
		{
			// simple factorization based on a list of primes
			// however, this will obviously fail on anything with a prime larger than 500.
			// My guess is that it's safe to ignore these because the LCM of anything
			// with a factor > 500 will not be viable anyway.
			int items = Array.BinarySearch(_primes, num);

			if (~_primes.Length == items)
			{
				IsFactorizable = false;
				Size = num;
				return;
			}

			if (items < 0)
				items = Array.BinarySearch(_primes, (int)Math.Sqrt(num));
			if (items < 0)
				items = ~items;

			IsFactorizable = true;
			Factors = new int[items + 2]; // max index + 1, +1 in case the flooring int cast above landed on a prime (e.g., num = 6)
			int remainder = num;

			for (int j = 0; j < _primes.Length && remainder != 1; ++j)
			{
				while (remainder % _primes[j] == 0)
				{
					++Factors[j];
					remainder /= _primes[j];
				}
			}

			Size = num;
			FactorCount = Factors.Sum();
		}

		public static FactorSet FromNumber(int num)
		{
			FactorSet fs = new FactorSet(null, 0);
			fs.InitializeFromNumber(num);

			return fs;
		}

		public FactorSet GetOverlap(FactorSet otherSet)
		{
			int[] smallerSet, largerSet;

			if (otherSet.Factors.Length > Factors.Length)
			{
				smallerSet = Factors;
				largerSet = otherSet.Factors;
			}
			else
			{
				smallerSet = otherSet.Factors;
				largerSet = Factors;
			}

			int[] newFactors = new int[largerSet.Length];

			int size = 1;
			for (int i = 0; i < smallerSet.Length; ++i)
				size *= newFactors[i] = Math.Abs(smallerSet[i] - largerSet[i]);
			for (int i = smallerSet.Length; i < largerSet.Length; i++)
				size *= newFactors[i] = largerSet[i];

			return new FactorSet(newFactors, size);
		}

		/// <summary>
		/// x.Difference(y) * X = y.Difference(x) * y = LCM(x, y)
		/// That is, the result contains all factors which are in Y but not X
		/// </summary>
		/// <param name="otherSet"></param>
		/// <returns></returns>
		FactorSet Difference(FactorSet otherSet)
		{
			if (!IsFactorizable || !otherSet.IsFactorizable)
				throw new InvalidOperationException("Cannot difference non-factorizable sets.");

			int maxLen = Math.Max(Factors.Length, otherSet.Factors.Length);
			int[] newFactors = new int[maxLen];
			int[] oFactors = otherSet.Factors;
			int size = 1;

			for (int i = 0; i < maxLen; ++i)
			{
				int lFactors = (i >= Factors.Length) ? 0 : Factors[i];
				int rFactors = (i >= oFactors.Length) ? 0 : oFactors[i];
				if (lFactors < rFactors)
				{
					newFactors[i] = rFactors - lFactors;
					size *= _primes[i] * newFactors[i];
				}
			}

			return new FactorSet(newFactors, size);
		}

		FactorSet Combine(FactorSet otherSet)
		{
			FactorSet newSet = new FactorSet(this);
			newSet.Add(otherSet);
			return newSet;
		}

		protected void Add(FactorSet otherSet)
		{
			if (!IsFactorizable || !otherSet.IsFactorizable)
				throw new InvalidOperationException("Cannot add non-factorizable sets.");

			int[] smallerSet, largerSet;

			if (otherSet.Factors.Length > Factors.Length)
			{
				smallerSet = Factors;
				largerSet = otherSet.Factors;
			}
			else
			{
				smallerSet = otherSet.Factors;
				largerSet = Factors;
			}

			int[] newFactors = new int[largerSet.Length];

			int size = 1;
			for (int i = 0; i < smallerSet.Length; ++i)
			{
				newFactors[i] = Math.Max(smallerSet[i], largerSet[i]);
				size *= newFactors[i] == 0 ? 1 : (int)Math.Pow(_primes[i], newFactors[i]);
			}
			for (int i = smallerSet.Length; i < largerSet.Length; i++)
			{
				newFactors[i] = largerSet[i];
				size *= newFactors[i] == 0 ? 1 : (int)Math.Pow(_primes[i], newFactors[i]);
			}

			Factors = newFactors;
			Size = size;
			FactorCount = Factors.Sum();
		}

		public static FactorSet operator +(FactorSet lhs, FactorSet rhs)
		{
			return lhs.Combine(rhs);
		}

		public static FactorSet operator -(FactorSet lhs, FactorSet rhs)
		{
			return lhs.Difference(rhs);
		}
	}

}
